/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:
 * Date: 2024-11-08
 * Time: 19:43
 */
class SparseMatrix {
    static class ColumnNode {
        int column;
        int value;
        ColumnNode next;

        ColumnNode(int column, int value) {
            this.column = column;
            this.value = value;
            this.next = null;
        }
    }

    static class RowNode {
        int row;
        ColumnNode firstColumn;

        RowNode(int row) {
            this.row = row;
            this.firstColumn = null;
        }
    }

    private int rows;
    private int columns;
    private RowNode[] matrix;

    public SparseMatrix(int rows, int columns) {
        this.rows = rows;
        this.columns = columns;
        this.matrix = new RowNode[rows];
        for (int i = 0; i < rows; i++) {
            matrix[i] = new RowNode(i);
        }
    }

    public void set(int row, int column, int value) {
        if (value == 0) return;
        RowNode rowNode = matrix[row];
        ColumnNode currentColumnNode = rowNode.firstColumn;
        ColumnNode previousColumnNode = null;

        while (currentColumnNode != null && column > currentColumnNode.column) {
            previousColumnNode = currentColumnNode;
            currentColumnNode = currentColumnNode.next;
        }

        if (currentColumnNode != null && currentColumnNode.column == column) {
            currentColumnNode.value = value;
        } else {
            ColumnNode newNode = new ColumnNode(column, value);
            if (previousColumnNode == null) {
                rowNode.firstColumn = newNode;
            } else {
                previousColumnNode.next = newNode;
            }
        }
    }

    public void printMatrix() {
        for (int i = 0; i < rows; i++) {
            RowNode rowNode = matrix[i];
            ColumnNode columnNode = rowNode.firstColumn;
            while (columnNode != null) {
                System.out.print(columnNode.value + " ");
                columnNode = columnNode.next;
            }
            System.out.println();
        }
    }
}
 public class Main {
    public static void main(String[] args) {
        SparseMatrix sparseMatrix = new SparseMatrix(4, 5);
        sparseMatrix.set(0, 1, 5);
        sparseMatrix.set(0, 3, 3);
        sparseMatrix.set(1, 0, 7);
        sparseMatrix.set(1, 2, 2);
        sparseMatrix.set(2, 4, 4);
        sparseMatrix.set(3, 1, 6);
        sparseMatrix.printMatrix();
    }
}
